package com.michael.leetcode;

import org.junit.Assert;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class Jump_45 {

    private static final Logger log = LoggerFactory.getLogger(Jump_45.class);

    /**
     * 45. 跳跃游戏 II
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     * 示例 1:
     * 输入: nums = [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     * 示例 2:
     * 输入: nums = [2,3,0,1,4]
     * 输出: 2
     * 提示:
     * 1 <= nums.length <= 104
     * 0 <= nums[i] <= 1000
     * 题目保证可以到达 nums[n-1]
     *
     * 本地能跳的最远下标 =  i+nums[i]
     * 那么再 {i+1 , i+nums[i] } 寻找下一个起跳点 直到结束
     *
     * 思路：从当前位置i开始跳一步可以到达的最远距离 =  i+ nums[i]
     *      判断是否可到达位置y   i+nums[i]>= y
     *      本题中 y =  nums.lenght-1
     * 
     *
     * 
     */
    public boolean jump(int[] numbs) {
        int n = numbs.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + numbs[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }




    @Test
    public void test(){
        int[] numbs = {2,9,6,5,7,0,7,2,7,9,3,2,2,5,7,8,1,6,6,6,3,5,2,2,6,3};
        boolean resule =  jump(numbs);
        log.info(String.valueOf(resule));

        numbs = new int[]{2, 0, 3, 1, 4};
        resule = jump(numbs);
        log.info(String.valueOf(resule));
    }
}
